|
In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix. An undirected graph has a symmetric adjacency matrix and therefore has real eigenvalues (the multiset of which is called the graph's ''spectrum'') and a complete set of orthonormal eigenvectors. While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant. Spectral graph theory is also concerned with graph parameters that are defined via multiplicities of eigenvalues of matrices associated to the graph, such as the Colin de Verdière number. ==Isospectral graphs== Two graphs are called isospectral or cospectral if the adjacency matrices of the graphs have equal multisets of eigenvalues. Isospectral graphs need not be isomorphic, but isomorphic graphs are always isospectral. The smallest pair of nonisomorphic cospectral undirected graphs is , comprising the 5-vertex star and the graph union of the 4-vertex cycle and the single-vertex graph, as reported by Collatz and Sinogowitz〔Collatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63–77, 1957.〕 in 1957. The smallest pair of nonisomorphic cospectral polyhedral graphs are enneahedra with eight vertices each.〔.〕 Almost all trees are cospectral, i.e., the share of cospectral trees on ''n'' vertices tends to 1 as ''n'' grows.〔Schwenk, A. J. "Almost All Trees are Cospectral" In: ''New Directions in the Theory of Graphs'' (F. Harary, Ed.), Academic Press, New York, 1973, pp. 275–307.〕 Isospectral graphs can also be constructed by means of the Sunada method.〔.〕 Another important source of isospectral graphs are the point-collinearity graphs and the line-intersection graphs of point-line geometries. These graphs are always isospectral but are often non-isomorphic. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Spectral graph theory」の詳細全文を読む スポンサード リンク
|